package com.squirrel.michale;

import java.util.ArrayDeque;
import java.util.Comparator;
import java.util.Deque;
import java.util.PriorityQueue;

/**
 * @author guanhao 观浩
 * @version 1.0.0.0
 * @createTime 2023/2/22 12:18 PM
 * @company Michale Squirrel
 * @link
 * @description
 */
public class LeetCode0230 {

    public int kthSmallest(TreeNode root, int k) {

        PriorityQueue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        Deque<TreeNode> d = new ArrayDeque<>();
        d.addLast(root);
        while (!d.isEmpty()) {
            TreeNode node = d.pollFirst();
            if (heap.size() < k) {
                heap.add(node.val);
            } else if (heap.peek() > node.val) {
                heap.poll();
                heap.add(node.val);
            }
            if (node.left != null) d.addLast(node.left);
            if (node.right != null) d.addLast(node.right);
        }
        return heap.peek();

    }
}
